package com.togo.algorithm.easy.tree;

import com.togo.algorithm.common.TreeNode;

import java.util.LinkedList;

/**
 * @Author taiyn
 * @Description 输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
 * <p>
 * 例如：
 * <p>
 * 给定二叉树 [3,9,20,null,null,15,7]，
 * <p>
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 返回它的最大深度 3 。
 * <p>
 *  
 * <p>
 * 提示：
 * <p>
 * 节点总数 <= 10000
 * @Date 9:13 AM 2023/5/26
 **/
public class Offer55 {

    /**
     * DFS
     *
     * @param root
     * @return
     */
    public int maxDepthByDFS(TreeNode root) {
        if (root == null) return 0;
        int left = maxDepthByDFS(root.left) + 1;
        int right = maxDepthByDFS(root.right) + 1;
        return Math.max(left, right);
    }

    /**
     * BFS
     * @param root
     * @return
     */
    public int maxDepthByBFS(TreeNode root) {
        if (root == null) return 0;
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int res = 0;
        while (!queue.isEmpty()) {
            res++;
            int n = queue.size();
            while (n > 0) {
                n--;
                TreeNode treeNode = queue.removeFirst();
                if (treeNode.left != null)
                    queue.addLast(treeNode.left);
                if (treeNode.right != null)
                    queue.addLast(treeNode.right);
            }
        }

        return res;
    }
}
